package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         216,
		Discription: "从1...9里选k个数使得和为n",
		Level:       2,
		Labels: map[string]int{
			"递归": 1,
			"去重": 1,
		},
	})
}

func CombinationSum3(k int, n int) [][]int {
	comb := make([]int, 0)
	res := make([][]int, 0)
	var travel func(int, int, int)
	travel = func(start int, count int, sum int) {
		if sum == n && count == k {
			res = append(res, append([]int(nil), comb...))
			return
		}

		if sum > n || count >= k {
			return
		}

		for i := start; i <= 9; i++ {
			comb = append(comb, i)
			travel(i+1, count+1, sum+i)
			comb = comb[:len(comb)-1]
		}
	}

	travel(1, 0, 0)
	return res
}
